//
// Created by 田建昆 on 2020/12/11.
//
#include <stdlib.h>
#include "priority_queue.h"

priority_queue *priority_queue_create(int size) {
    priority_queue *pq = malloc(sizeof(pq));
    pq->key = malloc(sizeof(int) * (size + 1));
    pq->n = 0;
    pq->size = size;

    return pq;
}

void priority_queue_insert(priority_queue *pq, int v) {
    int i = pq->n+1;
    // 不使用位置0
    // 根结点以1开始，那么i的父节点就是i/2。
    for (; i > 1 && pq->key[i/2] > v; i /= 2) {
        pq->key[i] = pq->key[i/2];
    }
    pq->key[i] = v;
    pq->n++;
}

int priority_queue_delmin(priority_queue *pq) {
    int min = pq->key[1];
    int last = pq->key[pq->n];
    pq->n--;
    int j;
    int k = 1;
    for (;2 * k <= pq->n; k = j) {
        // k的孩子就是2k和2k+1
        j = 2 * k;
        if (j != pq->n && pq->key[j] > pq->key[j + 1]) j++;
        if (last > pq->key[j]) pq->key[k] = pq->key[j];
        else break;
    }
    pq->key[k] = last;
    return min;
}